package com.lw.leetcode.dp.c;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * dp
 * 689. 三个无重叠子数组的最大和
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/8 10:49
 */
public class MaxSumOfThreeSubarrays {


    public static void main(String[] args) {
        MaxSumOfThreeSubarrays test = new MaxSumOfThreeSubarrays();

        // [0,3,5]  23
        int[] arr = {1, 2, 1, 2, 6, 7, 5, 1};
        int k = 2;

        // [0,2,4]  9
//        int[] arr = {1,2,1,2,1,2,1,2,1};
//        int k = 2;

        int[] ints = test.maxSumOfThreeSubarrays(arr, k);
        System.out.println(Arrays.toString(ints));
    }


    public int[] maxSumOfThreeSubarrays(int[] nums, int k) {
        int length = nums.length;
        int[] arr = new int[3];
        for (int i = 1; i < length; i++) {
            nums[i] += nums[i - 1];
        }
        int[] a = new int[length];
        int[] b = new int[length];
        int[] c = new int[length];
        a[0] = nums[k - 1];
        for (int i = 1; i <= length - 3 * k; i++) {
            a[i] = Math.max(nums[i + k - 1] - nums[i - 1], a[i - 1]);
        }
        for (int i = k; i <= length - 2 * k; i++) {
            b[i] = Math.max(nums[i + k - 1] - nums[i - 1] + a[i - k], b[i - 1]);
        }
        int max = 0;
        int index = 0;
        for (int i = k + k; i <= length - k; i++) {
            c[i] = Math.max(nums[i + k - 1] - nums[i - 1] + b[i - k], c[i - 1]);
            if (c[i] > max) {
                index = i;
                max = c[i];
            }
        }
        arr[2] = index;
        max = max - (nums[index + k - 1] - nums[index - 1]);
        for (int i = k; i <= length - 2 * k; i++) {
            if (b[i] == max) {
                index = i;
                break;
            }
        }
        arr[1] = index;
        max = max - (nums[index + k - 1] - nums[index - 1]);
        for (int i = 0; i <= length - 3 * k; i++) {
            if (a[i] == max) {
                index = i;
                break;
            }
        }
        arr[0] = index;
        return arr;
    }

}
